package com.kaifamiao.N0810;

import org.w3c.dom.Node;

/*
    栈
    队列
    链表，长度不固定
     */

public class NodeList {

    //链表中的第一个元素
    private Node head;

    //链表的最后一个元素
    private Node last;

    //记录链表的长度
    private int length;

    public boolean add(String value) {

        //创建一个节点，创建一个Node对象
        Node node = new Node(value);

        //链表中有元素吗
        if (head == null) {
            //链表中没有元素
            head = node;
        } else {
            //把元素添加进去
            last.next = node;
        }
        //把添加的元素作为链表的最后一个元素
        last = node;
        length++;

        return true;
    }

    public String remove(int index) {
        checkIndex(index);
        //被删除的元素
        Node current = null;
        if (index == 0) {
            //被删除的元素
            current = head;
            head = head.next;
        } else {
            //找被删除元素的前一个元素
            Node prev = head;
            for (int i = 1; i < index; i++) {
                prev = prev.next;
            }
            current = prev.next;
            //被删除的下一个元素
            Node next = current.next;
            //在链表中删除被删除的元素
            prev.next = next;
        }
        length--;
        return current.value;
    }

    public String set(int index, String value) {
        checkIndex(index);
        Node current = head;
        for (int i = 1; i <= index; i++) {
            current = current.next;
        }
        String old = current.value;
        current.value = value;
        return old;
    }

    public boolean add(int index, String value) {
        checkIndex0(index);
        Node add = new Node(value);
        if (index == 0) {
            add.next = head;
            head = add;
        } else if (index == length) {
            add(value);
        } else {
            Node prev = head;
            for (int i = 1; i < index; i++) {
                prev = prev.next;
            }
            Node current = prev.next;
            prev.next = add;
            add.next = current;
        }
        length++;
        return true;
    }

    private void checkIndex0(int index) {
        if (index < 0 || index > length) {
            throw new NodeListIndexOutOfBoundsException("索引异常，index应该是0到" + length + "但是接收到的是" + index);
        }
    }

    public String get(int index) {
        checkIndex(index);
        Node current = head;
        for (int i = 1; i <= index; i++) {
            current = current.next;
        }
        return current.value;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= length) {
            throw new NodeListIndexOutOfBoundsException("索引异常， index 应该是 0 到 " + (length - 1) + "。但是接收到的是 " + index);
        }
    }

    public int size() {
        return length;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("NodeList{");
        String str = "";
        if (head != null) {
            Node current = head;
            while (current != null) {
                sb.append(current + ",");
                current = current.next;
            }
            str = sb.substring(0, sb.length() - 1);
        } else {
            str = sb.toString();
        }
        str += "}";
        return str;
    }

    //链表中的每一个元素（节点）都是一个Node对象
    private class Node {

        //节点的值
        private String value;

        //下一个节点
        private Node next;

        public Node() {
        }

        public Node(String value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return this.value;
        }
    }

    private class NodeListIndexOutOfBoundsException extends IndexOutOfBoundsException {
        public NodeListIndexOutOfBoundsException(String msg) {
            super(msg);
        }
    }

}
